Search Results

Documents authored by Lynch, Christopher

Document
DOI: 10.4230/LIPIcs.FSCD.2021.19
An RPO-Based Ordering Modulo Permutation Equations and Its Applications to Rewrite Systems

Authors: Dohan Kim and Christopher Lynch

Published in: LIPIcs, Volume 195, 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)

Abstract
Rewriting modulo equations has been researched for several decades but due to the lack of suitable orderings, there are some limitations to rewriting modulo permutation equations. Given a finite set of permutation equations E, we present a new RPO-based ordering modulo E using (permutation) group actions and their associated orbits. It is an E-compatible reduction ordering on terms with the subterm property and is E-total on ground terms. We also present a completion and ground completion method for rewriting modulo a finite set of permutation equations E using our ordering modulo E. We show that our ground completion modulo E always admits a finite ground convergent (modulo E) rewrite system, which allows us to obtain the decidability of the word problem of ground theories modulo E.
Cite as

Dohan Kim and Christopher Lynch. An RPO-Based Ordering Modulo Permutation Equations and Its Applications to Rewrite Systems. In 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 195, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.FSCD.2021.19,
  author =	{Kim, Dohan and Lynch, Christopher},
  title =	{{An RPO-Based Ordering Modulo Permutation Equations and Its Applications to Rewrite Systems}},
  booktitle =	{6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-191-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{195},
  editor =	{Kobayashi, Naoki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2021.19},
  URN =		{urn:nbn:de:0030-drops-142572},
  doi =		{10.4230/LIPIcs.FSCD.2021.19},
  annote =	{Keywords: Recursive Path Ordering, Permutation Equation, Permutation Group, Rewrite System, Completion, Ground Completion}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.RTA.2010
LIPIcs, Volume 6, RTA'10, Complete Volume

Authors: Christopher Lynch

Published in: LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010)

Abstract
LIPIcs, Volume 6, RTA'10, Complete Volume
Cite as

Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{lynch:LIPIcs.RTA.2010,
  title =	{{LIPIcs, Volume 6, RTA'10, Complete Volume}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{6},
  editor =	{Lynch, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010},
  URN =		{urn:nbn:de:0030-drops-41003},
  doi =		{10.4230/LIPIcs.RTA.2010},
  annote =	{Keywords: Programming Techniques, Software Engineering, Programming Languages, Computation by Abstract Devices, Analysis of Algorithms and Problem Complexity Logics and Meanings of Programs, Mathematical Logic and Formal Languages, Symbolic and Algebraic Manipulation, Artificial Intelligence.}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.RTA.2010.i
Frontmatter (Titlepage, Table of Contents, Author List, PC List, Reviewer List)

Authors: Christopher Lynch

Published in: LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010)

Abstract
Front matter including table of contents, author list, PC list, and reviewer list.
Cite as

Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, pp. i-xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{lynch:LIPIcs.RTA.2010.i,
  author =	{Lynch, Christopher},
  title =	{{Frontmatter (Titlepage, Table of Contents, Author List, PC List, Reviewer List)}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{i--xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Lynch, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.i},
  URN =		{urn:nbn:de:0030-drops-26684},
  doi =		{10.4230/LIPIcs.RTA.2010.i},
  annote =	{Keywords: Table of Contents, Author List, PC List, Reviewer List}
}
Document
DOI: 10.4230/LIPIcs.RTA.2010.XIII
Preface

Authors: Christopher Lynch

Published in: LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010)

Abstract
Preface
Cite as

Christopher Lynch. Preface. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, pp. 13-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{lynch:LIPIcs.RTA.2010.XIII,
  author =	{Lynch, Christopher},
  title =	{{Preface}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{13--14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Lynch, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.XIII},
  URN =		{urn:nbn:de:0030-drops-26675},
  doi =		{10.4230/LIPIcs.RTA.2010.XIII},
  annote =	{Keywords: Preface}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact